Задача "Посчитай закономерность"
Постановка (kost) Как насчет вот такой задачки: "Посчитай закономерность". Есть последовательность из 1000-2000 чисел, в которой каждые 2-5 (число постоянное) чисел (числа целые, от 0 до 10000, а еще интереснее сделать любой длинны) идут по какому-то алгоритму, а потом по закономерности. Возможные операции - "+-*/" (деление целочисленное). Изначально ноль. Тоесть например если закономерность такая: +5 *60 /4 +18 +19 то входной файл будет 5 300 75 93 112 117 7020 1755 ... Задача - определить алгоритм. А потом будем расширять добавлением парочки новых операторов и т.п. и т.д. Если никто не против - могу накатать полное условие по-быстрячку и поехали) TODO: разобраться, как постить отформатированный код с подсветкой (raw non-escaped HTML or smth?) ACHTUNG!!! Не редактировать в rich editor'е! Он портит листинги! Нажимать в правом верхнем углу кнопочку с чёрненькой консолькой и редактировать сорсы. Примеры кодов вставлять внутрь Smalltalk/Seaside, danio, link (no sources)k Python, gromozeka, 25.07.2007, link , link2, link3, link4 , link5 def action(n1,n2): l=set([]) if n1 0 and n2 0:l|=set("*any") if n1<=n2:l|=set('+'+str(n2-n1)) else:l|=set('-'+str(n1-n2)) for (a,b,op) in (n1,n2,"*"),(n2,n1,'/'): if a!=0: arg=b/a if (op "*" and arg*a b) or (op "/" and arg!=0): l|=set(op+str(arg)) if (op "/" and b%a 0): if b/a<0:s=-1 else:s=1 a,b=abs(a),abs(b) for arg in xrange(b/(a+1)+1,b/a+1): l|=set(op+str(arg*s)) return l def my_and(x,y): res,tmp=x&y,lambda x:set(for e in list(x) if e[0 in '*/']) if '*any' in x: res|=tmp(y) if '*any' in y: res|=tmp(x) return res def nth(l,n,start): return [li for i in xrange(start,len(l),n)] def intr(l): return reduce(lambda x,y:my_and(x,y),l) def hypo(a,n): return for i in xrange(0,n) def find_alg(l): acts=[action(li-1,li) for i in xrange(1,len(l))] for i in xrange(1,len(acts)): if my_and(actsi,acts0)!=set([]): t=hypo(acts,i) if not(set([]) in t): acts=t; break return ''.join([el0 for el in map(list,acts)]) C++, D_K, 25.07.2007, link , link2, link3 class modif { struct data{ char c; int i; bool en_i; data():c(0),i(-1),en_i(false){} data(char c_, int i_, bool en_i_=true):c(c_),i(i_),en_i(en_i_){} int operator()(int i_)const{return c '+'? i_+i : c '-'? i_-i : c '*'? i_*i : i_/i;} bool find(int x,int y) { if(en_i) return (*this)(x) y; if( c '+' || c '-' || (c '*' && (abs(x)>abs(y) || !x && x!=y)) || (c '/' && (abs(y)>abs(x) || !y )) ) return false; i= c '/'? x/y : !x? 0: y/x; if(c '/'&&(!i || i 1)) return false; return true; } friend ostream& operator<<(ostream &os, const data &d){os<abs(x) && x && y%x 0) varn++ = data('*',y/x); if(abs(x)>abs(y) && y && x ) varn++ = (x%y 0)? data('/',x/y,false) : data('/',-1,false); } bool find(int x, int y) { for(active=0; active>i; if(i) return false; vector buf(1,i); int ni; while(!in.eof()){ in>>ni; buf.push_back(ni); } unsigned buf_i=1, buf_sz=buf.size(); vector alg; alg.push_back(modif(i,buf1)); i=bufbuf_i++; while(buf_i < buf_sz){ ni = bufbuf_i++; bool flg=alg0.find(i,ni); if(flg){ unsigned alg_sz=alg.size(); for(int p=0; p Python, Vladimir the Red Sunny, 25.07.2007, link import functools def evaluate_candidate(candidate, sequence, n): match = True for i in range(0, len(sequence)-1, n): if candidate(sequencei) != sequencei+1: match = False break return match def search(i_numbers, n): numbers = i_numbers: final_candidates = [] for i in range(n): candidates = [] def fn(a, b): return lambda x: x + a - b candidates.append( fn(numbersi+1, numbersi) ) candidates-1.description = " + " + `numbersi+1 - numbersi` if numbersi != 0: if numbersi+1%numbersi 0: def fn(a, b): return lambda x: x* (a / b) candidates.append( fn(numbersi+1, numbersi) ) candidates-1.description = " * " + `numbersi+1 / numbersi` if (numbersi+1 != 0) and (numbersi%numbersi+1 0): def fn(a, b): return lambda x: x / (a / b) candidates.append( fn(numbersi, numbersi+1) ) candidates-1.description = " / " + `numbersi / numbersi+1` eval_func = functools.partial(evaluate_candidate, sequence = numbersi:, n = n) tmp_candidates = filter(eval_func, candidates) if len(tmp_candidates) < 1: print "Error: no matches" return None if len(tmp_candidates) > 1: print "Error: more than one match" return None final_candidates.extend(tmp_candidates) return final_candidates #+5*60/4+18+19 n = 5 control_seq = 5, 300, 75, 93, 112, 117, 7020, 1755 ops = search(control_seq, n) if ops: s = "".join(for f in ops) print s else: print "Nothing found." Visual Prolog 7.x, Винитарх, 26.07.2007, link , link2, link3 , link4 open core,console,string,list,std domains pair = p(integer,integer). pair_list = pair*. pair_list_list = pair_list*. class predicates ку: (integer_list) -> string procedure. тесты: (pair_list_list) -> string nondeterm. тест: (pair_list,string,integer) nondeterm (i,i,i). oper: (pair,string,integer) nondeterm (i,o,o). check: (pair,string,integer) determ (i,i,i). выборки: (integer_list,integer,core::positive) -> pair_list_list procedure. выборка: (integer_list,integer,integer,core::positive) -> pair_list procedure. clauses ку(L)=A:-To= list::length(L)-2,A=тесты(выборки(L,To,fromto(1,To+1))),!. ку(_)="Ку". тесты(L)= concat(O,toString(A),тесты(L)):- oper(getMember_nd(V),O,A), тест(V,O,A). тесты([])="". тест(V,O,A):-check(P,O,A),!,тест(V,O,A). тест([],_,_). oper(p(X,Y),O,A):- X<=Y, A=Y-X, O="+"; X>Y, A=X-Y, O="-"; X<>0, A=Y quot X, Y rem X=0, O="*"; Y<>0, Arg=X quot Y, (Arg>=0, A=downTo(Arg,2); Arg<=0, A=fromTo(Arg,-2)), X quot A = Y, O="/". check(p(X,Y),O,A):- O="+", X+A=Y; O="-", X-A=Y; O="*", X*A=Y; O="/", X quot A=Y. выборки(L,To,Step)= |From=fromto(0,Step-1),X=выборка(L,From,To,Step). выборка(L,From,To,Step)= |I= fromtoInStep(From,To,Step), X=nth(I,L), Y=nth(I+1,L). Python, Кошмар, 27.07.2007, link , link2 (это не другая задача?) Lisp, DeefFinder, 27.07.2007, link (вроде, программа не обрабатывает много чего, стоит включать? - VtRS) C++, IL_Agent, 29.07.2007, link C, D_K, 01.08.2007, link Haskell, Vladimir the Red Sunny, 08.08.2007, link, link2, link3 (no source) Python (без лямбд), gromozeka, 12.08.2007, link K, zevun, 29.08.2007, link, link2 (вроде, всё, позже никто не решал?)